package leetcode

//https://leetcode.com/problems/longest-palindromic-substring/description/
/**
 * 最长回文子串
 *
 * abcdefgfedcba aaabbbeeeebbbaaa efafkefeogmaemg;seofefjiengnafjiejfiea;;gjg;;aeifjeijfangneijfefeingaejgienainfga
 */

val ss = "abcdefgfedcba aaabbbeeeebbbaaa efafkefeogmaemg;seofefjiengnafjiejfiea;;gjg;;aeifjeijfangneijfefeingaejgienainfga"
val lps = "abcacbaefjiejfijgnajgiang aaaaaacaaaaaacjeijfif"
fun main(args: Array<String>) {
    println(findLongestPalindromicSubstring("bb"))
}

//time complexity = o(n^2)
fun findLongestPalindromicSubstring(str: String): String {
    if (str.isEmpty())
        return str
    val charArray = str.toCharArray()
    var s: Int
    var e: Int

    var se: Int
    var ee: Int
    val maxLen = IntArray(4, { i -> 0 })
    for (i in 0..charArray.size) {
        //odd
        s = i - 1
        e = i + 1
        while (s >= 0 && e < charArray.size && charArray[s] == charArray[e]) {
            s--
            e++
        }
        if (e - s - 1 > maxLen[1] - maxLen[0]) {
            maxLen[0] = s + 1
            maxLen[1] = e
        }
        //even
        se = i
        ee = i + 1

        while (se >= 0 && ee < charArray.size && charArray[se] == charArray[ee]) {
            se--
            ee++
        }
        if (ee - se - 1 > maxLen[3] - maxLen[2]) {
            maxLen[2] = se + 1
            maxLen[3] = ee
        }

    }

    val maxS = if (maxLen[3] - maxLen[2] > maxLen[1] - maxLen[0]) maxLen[2] else maxLen[0]
    val maxE = if (maxLen[3] - maxLen[2] > maxLen[1] - maxLen[0]) maxLen[3] else maxLen[1]
    return str.substring(maxS, maxE)

}